home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 7 / Apprentice-Release7.iso / Environments / Clean 1.2.4 / Small Demos / war_seq.icl < prev   
Encoding:
Text File  |  1995-03-10  |  1.8 KB  |  64 lines  |  [TEXT/3PRM]
  1. module war_seq
  2.  
  3. /*
  4. Sequential version of Warshall's shortest path algorithm
  5.  
  6. Calculates the lenghts of the shortest paths between all nodes of
  7. a directed graph represented by its adjacency matrix using Warshall's
  8. algorithm. The result of the program will be a matrix containing the
  9. length of the shortest path between node i and node j on index (i,j).
  10.  
  11. Run the program with the Show Constructors option on (Application options)
  12. */
  13.  
  14. import StdClass; // RWS
  15. import StdInt
  16.  
  17. ::Row :== [Int]    // A row is represented as a list of integers.
  18. ::Mat :== [Row]    // A matrix is represented as a list of rows.
  19.  
  20. Size :== 6        // The size of the initial matrix.
  21.  
  22. //    The initial matrix.
  23.  
  24. InitMat::Mat                                //     Shortest path matrix:
  25. InitMat =    [[  0,100,100, 13,100,100  ],    // [  0, 16,100, 13, 20, 20 ]
  26.             [ 100,  0,100,100,  4,  9  ],    // [ 19,  0,100,  5,  4,  9 ]
  27.             [  11,100,  0,100,100,100  ],    // [ 11, 27,  0, 24, 31, 31 ]
  28.             [ 100,  3,100,  0,100,  7  ],    // [ 18,  3,100,  0,  7,  7 ]
  29.             [  15,  5,100,  1,  0,100  ],    // [ 15,  4,100,  1,  0,  8 ]
  30.             [  11,100,100, 14,100,  0 ]]    // [ 11, 17,100, 14, 21,  0 ]
  31.  
  32.  
  33. //    Miscellaneous functions.
  34.  
  35. Min::Int Int -> Int
  36. Min i j | i>j     =  j
  37.                 =  i
  38.  
  39. Select::[x] Int -> x 
  40. Select [f:r] 1 =  f
  41. Select [f:r] k =  Select r (k - 1)
  42.  
  43. //    Warshall's shortest path algorithm.
  44.  
  45. Warshall::Mat -> Mat
  46. Warshall mat =     Iterate 1 mat
  47.  
  48. Iterate::Int Mat -> Mat
  49. Iterate i mat    | i>Size     =  mat
  50.                             =  Iterate (i+1) (WarRows i mat (Select mat i))
  51.  
  52. WarRows::Int Mat Row -> Mat
  53. WarRows i [] rowi             =  []
  54. WarRows i [rowj:rs] rowi    =  [ UpdateRow (Select rowj i) rowj rowi : WarRows i rs rowi ]
  55.     
  56. UpdateRow::Int Row Row -> Row
  57. UpdateRow ji [] []                 =  []
  58. UpdateRow ji [jk:rjs] [ik:ris]    =  [ Min jk (ji + ik) : UpdateRow ji rjs ris ]
  59.  
  60. //    The Start rule: apply Warshall's algorithm on the initial matrix.
  61.  
  62. Start::Mat
  63. Start     = Warshall InitMat
  64.